package org.leetcode.middle.leetcode718;

public class    Solution {

    public int findLength3(int[] nums1, int[] nums2){

        int n = nums1.length;
        int m = nums2.length;
        int[][] dp = new int[n+1][m+1];
        int maxLength = 0;

        //dp[0][0]没有意义

        for (int i = 1; i <=n ; i++) {
            for (int j = 1; j <=m ; j++) {
                if (nums1[i-1]==nums2[j-1]){
                    dp[i][j]=dp[i-1][j-1]+1;
                    maxLength=Math.max(maxLength,dp[i][j]);
                }
            }
        }

        return maxLength;

    }

    public int findLength2(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int m = nums2.length;
        int[][] dp = new int[n][m];
        int maxLength = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (nums1[i]==nums2[j]){
                    if (i==0 || j==0){
                        dp[i][j]=1;
                    }else {
                        dp[i][j]=dp[i-1][j-1]+1;
                    }
                    maxLength=Math.max(maxLength,dp[i][j]);
                }
            }
        }

        return maxLength;
    }

    public int findLength(int[] nums1, int[] nums2) {

        int res = 0;

        //dp[i][j]的含义：以num1[i-1]为结尾的与num2[j-1]为结尾的最长子序列
        //dp[0][0]无意义，用0填充
        int[][] dp = new int[nums1.length + 1][nums2.length + 1];

        for (int i = 1; i <= nums1.length; i++) {
            for (int j = 1; j <= nums2.length; j++) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                res = Math.max(res, dp[i][j]);
            }
        }
        return res;
    }
}
